package com.test.daily.leetcode.y2022.m07.day0719.v03;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/19 上午 11:36
 * @version: 1.0
 */
public class Solution {
    // 定义Node
    public static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node lowest(Node head, Node o1, Node o2) {
        List<Node> list = new ArrayList<>();
        HashMap<Node, Node> map = new HashMap<>();
        map.put(head, null);
        putParent(map, head);
        return lowestAncestor(o1, o2, map);
    }

    public static Node lowestAncestor(Node o1, Node o2, HashMap<Node, Node> map) {
        HashSet o1Set = new HashSet();
        Node h1 = o1;
        while (h1 != null) {
            o1Set.add(h1);
            h1 = map.get(h1);
        }
        Node h2 = o2;
        while (!o1Set.contains(h2)) {
            h2 = map.get(h2);
        }
        return h2;
    }

    public static void putParent(HashMap<Node, Node> map, Node head) {
        if (head == null) {
            return;
        }
        if (head.left != null) {
            map.put(head.left, head);
            putParent(map, head.left);
        }
        if (head.right != null) {
            map.put(head.right, head);
            putParent(map, head.right);
        }
    }

    public static void prefill(Node head, List<Node> list) {
        if (head == null) {
            return;
        }
        prefill(head.left, list);
        list.add(head);
        prefill(head.right, list);
    }

    public static class Info {
        boolean findA;
        boolean findB;
        Node ans;

        public Info(boolean findA, boolean findB, Node ans) {
            this.findA = findA;
            this.findB = findB;
            this.ans = ans;
        }
    }

    public static Node lowest2(Node head, Node A, Node B) {
      return process(head, A, B).ans;
    }

    public static Info process(Node head, Node A, Node B) {
        if (head == null) {
            return new Info(false, false, null);
        }
        Node ans = null;
        Info leftInfo = process(head.left, A, B);
        Info rightInfo = process(head.right, A, B);
        boolean findA = leftInfo.findA || rightInfo.findA || head == A;
        boolean findB = rightInfo.findB || leftInfo.findB || head == B;

        if (leftInfo != null) {
            ans = leftInfo.ans;
        } else if (rightInfo != null) {
            ans = rightInfo.ans;
        } else {
            if (findA && findB) {
                ans = head;
            }
        }
        return new Info(findA, findB, ans);
    }

}
